package com.yoshino.leetcode.improve40.Threetysixth;

import java.util.Arrays;

class Solution {
    int[] ni = {0, 0, 1, -1}, nj = {1, -1, 0, 0};
    int[] color;

    public static void main(String[] args) {
        new Solution().isBipartite(new int[][]{{1, 3},{0, 2},{1, 3},{0, 2}});
        new Solution().updateMatrix(new int[][]{{1, 3},{0, 2},{1, 3},{0, 2}});
    }

    public int maxAreaOfIsland(int[][] grid) {
        // 深度遍历
        int res = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                res = Math.max(res, dfs(grid, i, j));
            }
        }
        return res;
    }

    private int dfs(int[][] grid, int i, int j) {
        // 用 grid 直接表示是否访问过
        if (i < 0 || j < 0 || i == grid.length || j == grid[0].length || grid[i][j] == 0) {
            return 0;
        }
        grid[i][j] = 0;
//        int res = 1;
//        for (int ind = 0; ind < 4; ind++) {
//            res += dfs(grid, i + ni[ind], j + nj[ind]);
//        }
//        // 不用复原，每个区域只遍历一次
//        return res;
        return 1 + dfs(grid, i + 1, j) + dfs(grid, i - 1, j) + dfs(grid, i, j + 1) + dfs(grid, i, j - 1);
    }

    public boolean isBipartite(int[][] graph) {
        // 二分图：每个边的两端分别属于不同的两个子集 -> 染色问题
        // 0：无色；1：红；2：绿
        // 深度遍历：该节点的相邻点 不可染不同颜色
        int n = graph.length;
        color = new int[n];
        boolean res = true;
        for (int i = 0; i < n && res; i++) {
            if (color[i] == 0) {
                res = dfs(1, i, graph);
            }
        }
        return res;
    }

    private boolean dfs(int col, int i, int[][] graph) {
        color[i] = col;
        int ncol = col == 1 ? 2 : 1;
        for (int ind : graph[i]) {
            if (color[ind] == 0) {
                if (!dfs(ncol, ind, graph)) {
                    return false;
                }
            } else if (color[ind] != ncol) {
                // 已经染色过
                return false;
            }
        }
        return true;
    }

    //动态规划可以看成是先从[0,0]位置往右下角更新一遍全部的距离，然后再从右下角[m-1, n-1]位置往左上方向去更新一遍，这样就能够实现用全部位置的0去DP计算最短距离。
    public int[][] updateMatrix(int[][] matrix) {
        // 从左上往右下，再从右下往左上
        // 点到左上距离0的最近距离
        int m = matrix.length, n = matrix[0].length;
        int[][] dis = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == 0) {
                    dis[i][j] = 0;
                } else {
                    dis[i][j] = Integer.MAX_VALUE / 2;
                }
            }
        }
        // 左上到右下
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i - 1 >= 0) {
                    // 离 左 0 的最小距离
                    dis[i][j] = Math.min(dis[i - 1][j] + 1, dis[i][j]);
                }
                if (j - 1 >= 0) {
                    dis[i][j] = Math.min(dis[i][j], dis[i][j - 1] + 1);
                }
            }
        }
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (i + 1 < m) {
                    dis[i][j] = Math.min(dis[i][j], dis[i + 1][j] + 1);
                }
                if (j + 1 < n) {
                    dis[i][j] = Math.min(dis[i][j], dis[i][j + 1] + 1);
                }
            }
        }
        return dis;
    }
}
